package com.lw.leetcode.dp.b;

/**
 * 213. 打家劫舍 II
 * 剑指 Offer II 090. 环形房屋偷盗
 *
 * @Author liw
 * @Date 2021/5/31 17:51
 * @Version 1.0
 */
public class Rob2 {

    public static void main(String[] args) {
        Rob2 test = new Rob2();
        int[] arr = {2, 3, 2};
//        int[] arr = {1,2,3,1};
//        int[] arr = {0};
//        int[] arr = {200,3,140,20,10};
        int rob = test.rob(arr);
        System.out.println(rob);
    }

    public int rob(int[] nums) {
        int l = nums.length;
        if (l == 1) {
            return nums[0];
        }
        if (l == 2) {
            return Math.max(nums[0], nums[1]);
        }
        if (l == 3) {
            return Math.max(Math.max(nums[0], nums[1]), nums[2]);
        }
        return Math.max(find(nums, 0, l - 2), find(nums, 1, l - 1));
    }

    private int find(int[] nums, int st, int end) {
        int l = end - st + 1;
        if (l == 2) {
            return Math.max(nums[st], nums[st + 1]);
        }
        if (l == 3) {
            return Math.max(nums[st] + nums[st + 2], nums[st + 1]);
        }
        int a = 0;
        int b = nums[st];
        int c = nums[st + 1];
        int index = st + 2;
        while (index <= end) {
            int item = Math.max(a, b) + nums[index];
            a = b;
            b = c;
            c = item;
            index++;
        }
        return Math.max(c, b);
    }
}
